use num::bigint::BigInt;
use std::time::Instant;
fn main() {
    let now = Instant::now();
    p001();
    p002();
    p003();
    p004();
    p005();
    p006();
    p007();
    p008();
    p009();
    p010();
    p011();
    p012();
    p013();
    p014();
    p015();
    p016();
    p017();
    p018();
    p019();
    p020();
    p021();
    println!("[Time: {} ms.]", now.elapsed().as_millis());
}

fn p001() {
    let mut sum = 0;
    for n in 1..1000 {
        if n % 3 == 0 || n % 5 == 0 {
            sum += n;
        }
    }
    println!("Problem 001: {}", sum);
}

fn p002() {
    let (mut a, mut b, mut sum) = (1, 1, 0);
    while a < 4000000 {
        let a_b = a + b;
        sum += a_b;
        a = b + a_b;
        b = b + a_b * 2;
    }
    println!("Problem 002: {}", sum);
}

fn p003() {
    let (mut n, mut d, mut x) = (600851475143i64, 0, 1);
    while n != 1 {
        d += 6;
        while n % (d - 1) == 0 {
            n = n / (d - 1);
            x = d - 1;
        }
        while n % (d + 1) == 0 {
            n = n / (d + 1);
            x = d + 1;
        }
    }
    println!("Problem 003: {}", x);
}

fn p004() {
    for a in (1..10).rev() {
        for b in (0..10).rev() {
            for c in (0..10).rev() {
                let p = a * 100001 + b * 10010 + c * 1100;
                for x in 100..1000 {
                    if p % x == 0 && p / x <= 999 {
                        println!("Problem 004: {}", p);
                        return;
                    }
                }
            }
        }
    }
}

fn p005() {
    let mut ans = 2520;
    for m in 11..21 {
        ans *= m / gcd(ans, m)
    }
    println!("Problem 005: {}", ans);
}

fn p006() {
    let mut sum = 0;
    for a in 1..100 {
        for b in (a + 1)..=100 {
            sum += 2 * a * b;
        }
    }
    println!("Problem 006: {}", sum)
}

fn p007() {
    let mut x = vec![2, 3, 5];
    let mut n = 7;
    while x.len() < 10001 {
        let mut add = false;
        for p in &x {
            if n % p == 0 {
                break;
            }
            if p * p > n {
                add = true;
                break;
            }
        }
        if add {
            x.push(n);
        }
        n += 2;
    }
    println!("Problem 007: {}", &x[x.len() - 1]);
}

fn p008() {
    let data=String::from("7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450");
    let (mut max, mut loc, mut count) = (1, 1, 0);
    let bytes = data.as_bytes();
    for (k, x) in bytes.iter().enumerate() {
        if x == &48 {
            (loc, count) = (1, 0);
            continue;
        }
        loc *= (x - 48) as i64;
        count += 1;
        if count == 13 {
            if loc > max {
                max = loc;
            }

            loc /= (bytes[k - 12]) as i64 - 48;
            count -= 1;
        }
    }
    println!("Problem 008: {}", max);
}

fn p009() {
    for c in 410..500 {
        for a in 1..=(1000 - c) / 2 {
            let b = 1000 - a - c;
            if b * b + a * a == c * c {
                println!("Problem 009: {}", a * b * c);
            }
        }
    }
}

fn p010() {
    let mut x = vec![2, 3, 5];
    let mut sum = 10i64;
    let mut n = 7;
    while n < 2000000 {
        let mut add = false;
        for p in &x {
            if n % p == 0 {
                break;
            }
            if p * p > n {
                add = true;
                break;
            }
        }
        if add {
            x.push(n);
            sum += n;
        }
        n += 2;
    }
    println!("Problem 010: {}", sum);
}

fn p011() {
    let data = [
        [
            8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8,
        ],
        [
            49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0,
        ],
        [
            81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65,
        ],
        [
            52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91,
        ],
        [
            22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80,
        ],
        [
            24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50,
        ],
        [
            32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70,
        ],
        [
            67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21,
        ],
        [
            24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
        ],
        [
            21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95,
        ],
        [
            78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92,
        ],
        [
            16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57,
        ],
        [
            86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
        ],
        [
            19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40,
        ],
        [
            4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
        ],
        [
            88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
        ],
        [
            4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36,
        ],
        [
            20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16,
        ],
        [
            20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54,
        ],
        [
            1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48,
        ],
    ];
    let mut max = 1;
    for i in 0..20 {
        for j in 0..17 {
            let (mut h, mut v, mut n, mut p) = (1, 1, 1, 1);
            for k in 0..4 {
                v *= data[j + k][i];
                h *= data[i][j + k];
                if i < 17 {
                    n *= data[i + k][j + k];
                    p *= data[i + k][j + 3 - k];
                }
            }
            if h > max {
                max = h;
            }
            if v > max {
                max = v;
            }
            if n > max {
                max = n;
            }
            if p > max {
                max = p;
            }
        }
    }
    println!("Problem 011: {}", max);
}

fn p012() {
    let mut s: i64 = 5;
    loop {
        s += 1;
        let n: i64 = s * (s + 1) / 2;
        let mut cnt: i64 = 2;
        for x in 2..n {
            if n % x == 0 {
                cnt += 2;
            }
            if n == x * x {
                cnt -= 1;
                break;
            }
            if n < x * x {
                break;
            }
        }
        if cnt > 500 {
            println!("Problem 012: {}", n);
            return;
        }
    }
}

fn p013() {
    let data: [&str; 100] = [
        "37107287533902102798797998220837590246510135740250",
        "46376937677490009712648124896970078050417018260538",
        "74324986199524741059474233309513058123726617309629",
        "91942213363574161572522430563301811072406154908250",
        "23067588207539346171171980310421047513778063246676",
        "89261670696623633820136378418383684178734361726757",
        "28112879812849979408065481931592621691275889832738",
        "44274228917432520321923589422876796487670272189318",
        "47451445736001306439091167216856844588711603153276",
        "70386486105843025439939619828917593665686757934951",
        "62176457141856560629502157223196586755079324193331",
        "64906352462741904929101432445813822663347944758178",
        "92575867718337217661963751590579239728245598838407",
        "58203565325359399008402633568948830189458628227828",
        "80181199384826282014278194139940567587151170094390",
        "35398664372827112653829987240784473053190104293586",
        "86515506006295864861532075273371959191420517255829",
        "71693888707715466499115593487603532921714970056938",
        "54370070576826684624621495650076471787294438377604",
        "53282654108756828443191190634694037855217779295145",
        "36123272525000296071075082563815656710885258350721",
        "45876576172410976447339110607218265236877223636045",
        "17423706905851860660448207621209813287860733969412",
        "81142660418086830619328460811191061556940512689692",
        "51934325451728388641918047049293215058642563049483",
        "62467221648435076201727918039944693004732956340691",
        "15732444386908125794514089057706229429197107928209",
        "55037687525678773091862540744969844508330393682126",
        "18336384825330154686196124348767681297534375946515",
        "80386287592878490201521685554828717201219257766954",
        "78182833757993103614740356856449095527097864797581",
        "16726320100436897842553539920931837441497806860984",
        "48403098129077791799088218795327364475675590848030",
        "87086987551392711854517078544161852424320693150332",
        "59959406895756536782107074926966537676326235447210",
        "69793950679652694742597709739166693763042633987085",
        "41052684708299085211399427365734116182760315001271",
        "65378607361501080857009149939512557028198746004375",
        "35829035317434717326932123578154982629742552737307",
        "94953759765105305946966067683156574377167401875275",
        "88902802571733229619176668713819931811048770190271",
        "25267680276078003013678680992525463401061632866526",
        "36270218540497705585629946580636237993140746255962",
        "24074486908231174977792365466257246923322810917141",
        "91430288197103288597806669760892938638285025333403",
        "34413065578016127815921815005561868836468420090470",
        "23053081172816430487623791969842487255036638784583",
        "11487696932154902810424020138335124462181441773470",
        "63783299490636259666498587618221225225512486764533",
        "67720186971698544312419572409913959008952310058822",
        "95548255300263520781532296796249481641953868218774",
        "76085327132285723110424803456124867697064507995236",
        "37774242535411291684276865538926205024910326572967",
        "23701913275725675285653248258265463092207058596522",
        "29798860272258331913126375147341994889534765745501",
        "18495701454879288984856827726077713721403798879715",
        "38298203783031473527721580348144513491373226651381",
        "34829543829199918180278916522431027392251122869539",
        "40957953066405232632538044100059654939159879593635",
        "29746152185502371307642255121183693803580388584903",
        "41698116222072977186158236678424689157993532961922",
        "62467957194401269043877107275048102390895523597457",
        "23189706772547915061505504953922979530901129967519",
        "86188088225875314529584099251203829009407770775672",
        "11306739708304724483816533873502340845647058077308",
        "82959174767140363198008187129011875491310547126581",
        "97623331044818386269515456334926366572897563400500",
        "42846280183517070527831839425882145521227251250327",
        "55121603546981200581762165212827652751691296897789",
        "32238195734329339946437501907836945765883352399886",
        "75506164965184775180738168837861091527357929701337",
        "62177842752192623401942399639168044983993173312731",
        "32924185707147349566916674687634660915035914677504",
        "99518671430235219628894890102423325116913619626622",
        "73267460800591547471830798392868535206946944540724",
        "76841822524674417161514036427982273348055556214818",
        "97142617910342598647204516893989422179826088076852",
        "87783646182799346313767754307809363333018982642090",
        "10848802521674670883215120185883543223812876952786",
        "71329612474782464538636993009049310363619763878039",
        "62184073572399794223406235393808339651327408011116",
        "66627891981488087797941876876144230030984490851411",
        "60661826293682836764744779239180335110989069790714",
        "85786944089552990653640447425576083659976645795096",
        "66024396409905389607120198219976047599490197230297",
        "64913982680032973156037120041377903785566085089252",
        "16730939319872750275468906903707539413042652315011",
        "94809377245048795150954100921645863754710598436791",
        "78639167021187492431995700641917969777599028300699",
        "15368713711936614952811305876380278410754449733078",
        "40789923115535562561142322423255033685442488917353",
        "44889911501440648020369068063960672322193204149535",
        "41503128880339536053299340368006977710650566631954",
        "81234880673210146739058568557934581403627822703280",
        "82616570773948327592232845941706525094512325230608",
        "22918802058777319719839450180888072429661980811197",
        "77158542502016545090413245809786882778948721859617",
        "72107838435069186155435662884062257473692284509516",
        "20849603980134001723930671666823555245252804609722",
        "53503534226472524250874054075591789781264330331690",
    ];
    let mut sum: i64 = 0;
    for v in data {
        sum += v[0..11].parse::<i64>().unwrap();
    }
    println!("Problem 013: {}", &(sum.to_string())[0..10]);
}

fn p014() {
    let mut l: i64 = 1;
    let mut i: i64 = 1;
    for s in 500000..1000000 {
        let r = collatz_seq_len(s);
        if r > l {
            (l, i) = (r, s);
        }
    }
    println!("Problem 014: {}", i);
}

fn p015() {
    let ans: i64 = 4 * 5 * 7 * 23 * 29 * 31 * 33 * 37 * 39;
    println!("Problem 015: {}", ans);
}

fn p016() {
    let mut one = BigInt::parse_bytes(b"1", 10).expect("It must be a big int.");
    one <<= 1000;
    let mut sum: u32 = 0;
    for i in one.to_string().bytes() {
        sum += (i - 48) as u32;
    }
    println!("Problem 016: {}", sum);
}

fn p017() {
    let mut sum = 0;
    for i in 1..1001 {
        let s = spell(i);
        let n = count(&s);
        sum += n;
    }
    println!("Problem 017: {}", sum);
}

fn p018() {
    let mut data: [[i32; 15]; 15] = [
        [75, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [95, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [17, 47, 82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [18, 35, 87, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [20, 4, 82, 47, 65, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [19, 1, 23, 75, 3, 34, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [88, 2, 77, 73, 7, 63, 67, 0, 0, 0, 0, 0, 0, 0, 0],
        [99, 65, 4, 28, 6, 16, 70, 92, 0, 0, 0, 0, 0, 0, 0],
        [41, 41, 26, 56, 83, 40, 80, 70, 33, 0, 0, 0, 0, 0, 0],
        [41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 0, 0, 0, 0, 0],
        [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 0, 0, 0, 0],
        [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 0, 0, 0],
        [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 0, 0],
        [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 0],
        [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23],
    ];
    for r in (1..15).rev() {
        for c in 0..r {
            if data[r][c] > data[r][c + 1] {
                data[r - 1][c] += data[r][c]
            } else {
                data[r - 1][c] += data[r][c + 1]
            }
        }
    }
    println!("Problem 018: {}", data[0][0]);
}

fn p019() {
    let (mut count, mut d) = (0, 1);
    for y in 1901..2001 {
        for m in 1..=12 {
            match m {
                1 | 3 | 5 | 7 | 8 | 10 | 12 => d += 31,
                4 | 6 | 9 | 11 => d += 30,
                2 => {
                    if y % 4 == 0 && y % 100 != 0 || y % 400 == 0 {
                        d += 29;
                    } else {
                        d += 28;
                    }
                }
                _ => (),
            }
            if d % 7 == 5 {
                count += 1;
            }
        }
    }
    println!("Problem 019: {}", count);
}

fn p020() {
    let mut hundred = BigInt::parse_bytes(b"10", 10).expect("It must be a number");
    for x in 2..100 {
        hundred *= x;
    }
    let mut sum: u32 = 0;
    for i in hundred.to_string().bytes() {
        sum += (i - 48) as u32;
    }

    println!("Problem 020: {}", sum);
}

fn spell(n: i32) -> String {
    let words = [
        "",
        "one",
        "two",
        "three",
        "four",
        "five",
        "six",
        "seven",
        "eight",
        "nine",
        "ten",
        "eleven",
        "twelve",
        "thirteen",
        "fourteen",
        "fifteen",
        "sixteen",
        "seventeen",
        "eighteen",
        "nineteen",
    ];
    if n < 20 {
        return words[n as usize].to_string();
    }
    if n > 19 && n < 100 {
        let (ones, tens) = (n % 10, n / 10);
        return match tens {
            2 => format!("twenty {}", spell(ones)),
            3 => format!("thirty {}", spell(ones)),
            4 => format!("forty {}", spell(ones)),
            5 => format!("fifty {}", spell(ones)),
            6 => format!("sixty {}", spell(ones)),
            7 => format!("seventy {}", spell(ones)),
            8 => format!("eighty {}", spell(ones)),
            9 => format!("ninety {}", spell(ones)),
            _ => "".to_string(),
        };
    }

    if n > 99 && n < 1000 {
        let (ending, hundreds) = (n % 100, n / 100);
        let mut end_spell = String::new();
        if ending != 0 {
            end_spell = format!(" and {}", spell(ending));
        }
        return format!("{} hundred {}", spell(hundreds), end_spell);
    }
    if n == 1000 {
        return "one thousand".to_string();
    }
    return "".to_string();
}

fn count(word: &str) -> i32 {
    if word.eq("") {
        return 0;
    }
    if word[0..1].eq(" ") {
        return count(&word[1..]);
    }
    return 1 + count(&word[1..]);
}

fn collatz_seq_len(mut s: i64) -> i64 {
    let mut l: i64 = 1;
    while s != 1 {
        if s % 2 == 0 {
            s /= 2;
        } else {
            s = 3 * s + 1;
        }
        l += 1;
    }
    l
}

fn gcd(x: i64, y: i64) -> i64 {
    let r = x % y;
    if r == 0 {
        y
    } else {
        gcd(y, r)
    }
}


fn p021() {
    let mut sl = [0; 10000];
    for n in 220..10000 {
        sl[n] = sum_proper_divisors(n as i32);
    }
    let mut ans = 0;
    for n in 220..10000 {
        if sl[n] >= 10000 {
            continue;
        }
        let temp = sl[n] as usize;
        if sl[temp] == n as i32 && temp != n {
            ans += n;
        }
    }
    println!("Problem 021: {}", ans);
}

fn sum_proper_divisors(n: i32) -> i32 {
    if is_prime(n) {
        return 1;
    }
    let mut result: i32 = 1;
    let mut x: i32 = 2;
    while x * x < n {
        if n % x == 0 {
            result += x + n / x;
        }
        x += 1;
    }
    if x * x == n {
        result += x;
    }
    return result;
}

fn is_prime(n: i32) -> bool {
    if n <= 1 {
        return false;
    }
    if n % 2 == 0 || n % 3 == 0 {
        return n == 2 || n == 3;
    }
    let mut x = 6;
    while x * x - 2 * x + 1 <= n {
        if n % (x - 1) == 0 || n % (x + 1) == 0 {
            return false;
        }
        x += 6;
    }
    return true;
}
